package Topological;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Created with Intellij IDEA.
 * Description;
 * User:TQ02
 * Data:2024-03-14
 * Time:15:19
 * Text：207. 课程表
 */
public class Text1 {
    public boolean canFinish(int n, int[][] prerequisites) {

        //第一步，构造图
        HashMap<Integer, List<Integer>> map=new HashMap<>();  //记录出度的结点
        int[] in=new int[n];   //记入度
        for(int[] array: prerequisites){
            int x=array[0],y=array[1];   //从y到x
            if(!map.containsKey(y)){
                map.put(y,new LinkedList<>());
            }
            map.get(y).add(x);
            in[x]++;
        }


        //第二步，将度为0的结点加入队列当中
        Queue<Integer> t1=new LinkedList<>();
        for(int k=0;k<n;k++){
            if(in[k]==0){
                t1.add(k);
            }

        }
        while(!t1.isEmpty()){
            int a=t1.poll();
            //判断入读为0的结点，取消之后的出度结点线
            for(int c:map.getOrDefault(a,new LinkedList<>())){
                //连接的结点的入度会减一
                in[c]--;
                if(in[c]==0){
                    t1.add(c);
                }
            }
        }
        for(int k:in){
            if(k!=0) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        int[][] te={{0,1}};
        Text1 t1=new Text1();
        t1.canFinish(2,te);
    }
}
